package com.Oct_Nighteen;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Solution768 {

    /**
     * 直接使用数组前缀和
     *
     * 2022/10/19 23:28
     * @param arr
     * @return
     */

    public int maxChunksToSorted(int[] arr) {
        int res=0;
        int[] cnt=new int[arr.length];
        System.arraycopy(arr, 0, cnt, 0, arr.length);
        long sum1=0,sum2=0;
        Arrays.sort(arr);
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(cnt));
        for (int i=0;i<arr.length;i++)
        {
            sum1+=arr[i];
            sum2+=cnt[i];
            if (sum1==sum2) res++;
        }
        return res;
    }

    /**
     * 用栈进行的操作
     *
     * 2022/10/19 23:47
     * @param arr
     * @return
     */

    public int maxChunksToSorted1(int[] arr) {
        Deque<Integer> deque=new LinkedList<>();
        for (int num:arr)
        {
            if (!deque.isEmpty()&&deque.getLast()>num)
            {
                int cur=deque.getLast();
                while(!deque.isEmpty()&&deque.getLast()>num) deque.removeLast();
                deque.add(cur);
            }else
            {
                deque.add(num);
            }
        }
        return deque.size();
    }

    public static void main(String[] args) {
        Solution768 solution768=new Solution768();
        System.out.println(solution768.maxChunksToSorted1(new int[]{4,2,2,1,1}));
    }

}
